public class test {
    //leetcode 64.最小路径和
    class Solution {
        public int minPathSum(int[][] grid) {
            // 1. 创建dp[][]表
            int m = grid.length;
            int n = grid[0].length;
            int[][] dp = new int[m][n+1];
            // 2. 初始化
            dp[0][1] = grid[0][0];
            for(int i = 1;i <= n;i++){
                dp[0][i] = dp[0][i-1] + grid[0][i-1];
            }
            for(int i = 0;i < m;i++){
                dp[i][0] = Integer.MAX_VALUE;
            }
            // 3. 填表
            for(int i = 1;i < m;i++){
                for(int j = 1;j <= n;j++){
                    dp[i][j] = Math.min(dp[i][j-1],dp[i-1][j]) + grid[i][j-1];
                }
            }
            // 4. 返回值
            return dp[m-1][n];
        }
    }
    //leetcode 174.地下城游戏
    class Solution {
        public int calculateMinimumHP(int[][] dungeon) {
            // 1. 创建dp[][]表
            int m = dungeon.length;
            int n = dungeon[0].length;
            // 创建右,下两边的辅助边框
            int[][] dp = new int[m+1][n+1];
            // 2. 初始化
            // (dp[i][j]代表以该位置为起点,到达终点所需最低健康点)
            for(int i = 0;i <= m;i++){
                dp[i][n] = Integer.MAX_VALUE;
            }
            for(int i = 0;i <= n;i++){
                dp[m][i] = Integer.MAX_VALUE;
            }
            //保证右下角起点值为正确的
            dp[m][n-1] = 0;
            // 3. 填表
            for(int i = m - 1;i >= 0;i--){
                for(int j = n - 1;j >= 0;j--){
                    dp[i][j] = Math.min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j];
                    if(dp[i][j] < 0){
                        dp[i][j] = 0;
                    }
                }
            }
            // 4. 返回值
            return dp[0][0] > 0 ? dp[0][0] + 1 : 1;
        }
    }
    //leetcode 3446.按对角线进行矩阵排序(周赛)
    class Solution {
        public int[][] sortMatrix(int[][] grid) {
            int n = grid.length;
            if (n == 0)
                return grid;
            // 处理左下角对角线（包括主对角线）
            for (int i = 0; i < n; i++) {
                sortDiagonal(grid, i, 0, false); // 非递增排序
            }
            for (int j = 1; j < n; j++) {
                sortDiagonal(grid, 0, j, false); // 非递增排序
            }
            // 处理右上角对角线（不包括主对角线）
            for (int j = 1; j < n; j++) {
                sortDiagonal(grid, 0, j, true); // 非递减排序
            }
            for (int i = 1; i < n; i++) {
                sortDiagonal(grid, i, n - 1, true); // 非递减排序
            }
            return grid;
        }

        public static void sortDiagonal(int[][] grid, int row, int col, boolean ascending) {
            List<Integer> diagonal = new ArrayList<>();
            int i = row, j = col;
            while (i < grid.length && j < grid[0].length) {
                diagonal.add(grid[i][j]);
                i++;
                j++;
            }
            if (ascending) {
                Collections.sort(diagonal); // 非递减排序
            } else {
                Collections.sort(diagonal, Collections.reverseOrder()); // 非递增排序
            }
            i = row;
            j = col;
            int index = 0;
            while (i < grid.length && j < grid[0].length) {
                grid[i][j] = diagonal.get(index++);
                i++;
                j++;
            }
        }
    }
    //leetcode 274.H指数
    class Solution {
        public int hIndex(int[] citations) {
            int len = citations.length;
            int[] nums = new int[len + 1];
            for(int i = 0;i < len;i++){
                nums[Math.min(citations[i],len)]++;
            }
            int s = 0;
            for(int i = len;i >= 0;i--){
                s += nums[i];
                if(s >= i){
                    return i;
                }
            }
            return -1;
        }
    }
}
